﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class HeapSortMedianSearch
    {
        internal static float medianHeapSortSelect(int[] numbers)
        {
            heapSort(numbers);
            float median = numbers[(numbers.Length - 1) / 2];
            if(numbers.Length % 2 == 0) {
                float leftMedian  = numbers[( numbers.Length - 1) / 2];
                float rightMedian = numbers[((numbers.Length - 1) / 2) + 1];
                median = (leftMedian + rightMedian) / 2;
            }
            else {
                median = numbers[(numbers.Length - 1) / 2];
            }
            Console.WriteLine(String.Format("Median calculated by heap sort is: {0}", median));
            return median;
        }

        private static void heapSort(int[] E)
        {
            buildMaxHeap(E);
            int heapSize = E.Length;
            for(int i = E.Length - 1; i > 0 ; --i)
            { 
                swap(E, i, 0);
                heapSize--;
                maxHeapify(E, 0, heapSize);
            }
        }

        private static void buildMaxHeap(int[] E)
        { 
            for(int i = (E.Length / 2) - 1; i >= 0; --i) {
                maxHeapify(E, i, E.Length);
            }
        }

        private static void maxHeapify(int [ ] E, int root, int heapsize)
        { 
            int max;
            int left = (2 * (root + 1)) - 1;
            int right = 2 * (root + 1);
            if((left < heapsize) && (E[left] > E[root])) {
                max = left;
            }
            else {
                max = root;
            }
            if ((right < heapsize) && (E[right] > E[max])) {
                max = right;
            }
            if(max != root)
            { 
                swap(E, root, max);
                maxHeapify(E, max, heapsize);
            }
        }

        private static void swap(int[] E, int index1, int index2)
        {
            int temp  = E[index1];
            E[index1] = E[index2];
            E[index2] = temp;
        }
    }
}
